package character;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;


/**
 * This class represents an NFA.  An NFA has a list of states and a list of internal NFAs.
 * @author Matt
 *
 */
public class NFA {
	//NFA will be treated like a graph.
//	Queue queue;
	List<State> States;//List of States in NFA
	private List<NFA> internalNFAs = null;
	//General idea:
	//[List] = List of valid end states
	
	//Constructors:
	/**
	 * Basic NFA Constructor.  
	 */

	public NFA(){
		States = new ArrayList<State>();
	}
	
	
	/**
	 * Gets internal NFAs
	 * @return
	 */
	public List<NFA> getInternalNFAs() {
		return internalNFAs;
	}


	/**
	 * Sets internal NFAs
	 * @param internalNFAs
	 */
	public void setInternalNFAs(List<NFA> internalNFAs) {
		this.internalNFAs = internalNFAs;
	}
	
	/**
	 * Adds an internal NFA to current NFA
	 * @param newNFA
	 */
	public void addInternalNFA(NFA newNFA){
		this.internalNFAs.add(newNFA);
	}

	//Methods:
	
	/**
	 * Adds a state to the NFA
	 * @param state
	 */
	public void addState(State state){
		//Adds a state.
		if(!this.States.contains(state)){
		this.States.add(state);
		}
	}
	
	/**
	 * Does an NFA merge of a union operation with the two NFAs.
	 * @param firstNFA
	 * @param secondNFA
	 * @return
	 */
	public static NFA mergeUnion(NFA firstNFA, NFA secondNFA){
		
		//Take the startState of firstNFA, link it with the startState of secondNFA
		
		
		int firstSize = firstNFA.States.size();
		int secSize = secondNFA.States.size();
		State secStart = null;
		
		//Find second start state.
		for(int k=0; k<secSize; k++){
			State state = secondNFA.States.get(k);
			//state.setID(firstSize+state.getID());	//Sets new id for second NFA
			firstNFA.addState(state);
			if(state.isStartState()){
				secStart = state;
				secStart.setStartState(false);
			//	break;
			}
		}

		//Find first start state
		Input input = new Input("Epsilon", secStart);
		for(int k=0; k<firstSize; k++){
			State state =firstNFA.States.get(k);
			if(state.isStartState()){
				state.addInput(input);
				break;
			}
		}			
		return firstNFA;
	}
	
	/**
	 * Does an NFA merge of concatenation for two NFAs.  The second NFA is concatted to the first NFA.
	 * @param firstNFA
	 * @param secondNFA
	 * @return
	 */
	public static NFA mergeConcat(NFA firstNFA, NFA secondNFA){
		int firstSize = firstNFA.States.size();
		int secSize = secondNFA.States.size();
		State secStart = null;

		//Get second NFA start state
		for(int k=0; k<secSize; k++){
			State state = secondNFA.States.get(k);
			//state.setID(firstSize+state.getID());
			firstNFA.addState(state);
			if(state.isStartState()){
				secStart = state;
//				break;
			}
		}
		Input input = new Input("Epsilon", secStart);
		secStart.setStartState(false);
		for(int k=firstSize-1; k>=0; k--){
			State state = firstNFA.States.get(k);
			if(state.isFinishState()){
				state.setFinishState(false);
				state.addInput(input);
			}
		}
		
		return firstNFA;
	}
	//*/+: Make it a * or + (Use only 1 NFA)
	
	// ? Do something for this symbol (1 NFA)
	
	/**
	 * Does a marge operation with a star operator.
	 * @param firstNFA
	 * @return
	 */
	public static NFA mergeStar(NFA firstNFA){
		int firstSize = firstNFA.States.size();	//Size of NFA
		State firstStart = null;	//Starting state

		//Determine start state.  Add empty string to cycle to itself and set start state to finish state.
		for(int k=0; k<firstSize; k++){
			State state = firstNFA.States.get(k);
			if(state.isStartState()){
				firstStart = state;
			}
		}

		Input input = new Input("Epsilon", firstStart);
		//Determine finishing states and add input to start state.
		for(int k=firstSize-1; k>=0; k--){
			State state = firstNFA.States.get(k);
			if(state.isFinishState()){
				state.addInput(input);
			}
		}
		

		firstStart.setFinishState(true);
		return firstNFA;
	}
	
	/**
	 * Merges an NFA based on the '+' character.
	 * @param firstNFA
	 * @return
	 */
	public static NFA mergePlus(NFA firstNFA){

		int firstSize = firstNFA.States.size();	//Size of NFA
		State firstStart = null;	//Starting state
		//Determine start state.  Add empty string to cycle to itself and set start state to finish state.
		for(int k=0; k<firstSize; k++){
			State state = firstNFA.States.get(k);
			if(state.isStartState()){
				firstStart = state;
				break;
			}
		}
		Input input = new Input("Epsilon", firstStart);

		//Determine finishing states and add input to start state.
		for(int k=firstSize-1; k>=0; k--){
			State state = firstNFA.States.get(k);
			if(state.isFinishState()){
				state.addInput(input);
			}
		}
		
		return firstNFA;
	}
	
	/**
	 * Returns the state with the given ID
	 * @param id of the state we wish to return
	 * @return
	 */
	public State getState(int id){
		
		int x=this.States.size();
		for(int k=0; k<x; k++){
			if(this.States.get(k).getID()==id){
				return this.States.get(k);
			}
		}
		
		//TRY/CATCH?
		System.out.println("State not found");
		return null;
	}
	
	/**
	 * Returns list of states in NFA
	 * @return
	 */
	public List<State> getStates(){
		return this.States;
	}
	
	/**
	 * Removes a state with the specified ID.  It also removes the iputs from the states that points
	 * to that specific state.
	 * @param ID
	 */
	public void removeState(int ID){
		int numStates = this.States.size();
		
		for(int k=0; k<numStates; k++){
			State state = this.States.get(k);
			List<Input> stateInputs = state.getInputs();
			for(int i=0; i<stateInputs.size(); i++){
				if(stateInputs.get(i).getNextState().getID()==ID){
					stateInputs.remove(i);
				}
			}
			if(state.getID()==ID){
				this.States.remove(k);
			}
		}
	}
	
	/**
	 * Converts the current NFA to a DFA
	 * @return a DFA
	 */ 
	
	public DFA toDFA()
	{
		//DFAStatesList: List of potential DFA states (as multi-NFAs)
		//InputTitles: List of inputTitles
		//TraverseResult: List of multi-NFA states that are the result of following to nextState
		
		List<List<State>> DFAStatesList = new ArrayList<List<State>>();	//List of DFA States (as multiple equivalent NFA states)
		List<String> InputTitles = new ArrayList<String>();	//List of input titles
		Queue<List<State>> TraversingResult = new LinkedList<List<State>>();	//List of multi-NFA states that are the result of following to nextState.
		List<State> TrueDFAList = new ArrayList<State>();	//List of DFA States (as single DFA State)
		int stateNum = 0;
		//Number of states for the NFA
		int numStates = this.States.size();
		State startState=null;
		
		/*GET THE STARTING DFA STATE*/
		for(int k=0; k<numStates; k++){
			State state = this.States.get(k);
			if(state.isStartState()){
				startState = state;
				break;
			}
		}
		
		removeEpsilons();
		
		TrueDFAList = DFACreation(startState);
		
		DFA returnDFA = new DFA(TrueDFAList);
		return returnDFA;
	}
	
	private void removeEpsilons() {
		int numStates = this.States.size();
		State startState = null;
		for(int k=0; k < numStates; k++){
			State state = this.States.get(k);
			if(state.isStartState()){
				startState = state;
				break;
			}
		}
		
		for (int k = 0; k < this.States.size(); k++) {
			State state = this.States.get(k);
			for (int j = 0; j < state.getInputs().size(); j++) {
				Input input = state.getInputs().get(j);
				if (input.getTitle().equals("Epsilon")) {
					boolean stateStays = false;
					state.getInputs().remove(j);
					j--;
					if (input.getNextState().equals(state)) {
						continue;
					}
//					if (input.getNextState().isStartState()) {
//						state.setStartState(true);
//					}
					if (input.getNextState().isFinishState()) {
						state.setFinishState(true);
					}
					for (Input targetInput : input.getNextState().getInputs()) {
						state.addInput(targetInput);
					}
					
//					for (State searchState : this.States) {
//						for (Input searchInput : searchState.getInputs()) {
//							if (searchInput.nextState.equals(input.getNextState())) {
//								searchInput.setNextState(state);
//							}
//						}
//					}
//					int i = 0;
//					for (State searchState : this.States) {
//						if (input.getNextState().equals(searchState)) {
//							break;
//						}
//						i++;
//					}
//					this.States.remove(i);
				}
			}
		}
	}
	
	/**
	 * Finds the start state, throws it on a stack.
	 * It then pops that state off the stack, and turns all it's inputs into new 'master states'
	 * These master states contain references to the old versions that they replace
	 * 
	 * One the master list is compiled, all master states are checked to ensure that everything is properly linked
	 * This master list is then returned.
	 * @param startState
	 * @return
	 */
	private List<State> DFACreation(State startState){
		int stateNum = 0;
		List<State> TrueDFAList = new ArrayList<State>();	//List of DFA States (as single DFA State)
		Stack<State> masterStack = new Stack<State>();
		
		//State currState = startState;
		//State currState = new State(stateNum++,startState.getInputs());
		State currState = new State(stateNum++);
		currState.setStartState(true);
		currState.addID(startState.getID());
		for (Input i: startState.getInputs()){
			currState.addOldInput(i);
		}
		TrueDFAList.add(currState);
		masterStack.push(currState);
		//int numStates = this.States.size();
		/*
		 * While there are still nodes to process, keep on keeping on.
		 */
		while (!masterStack.empty()){
			currState = masterStack.pop();
			//Create Master List for the current node
			List<Queue<Input>> masterInputList = new ArrayList<Queue<Input>>();
			//Fill that there Master List for the current node
			//for (Input i: currState.getInputs()){
			for (Input i: currState.getOldInputs()){
				boolean found = false;
				//For each queue in the master state input list
				for (Queue<Input> q: masterInputList){
					// if the title of the first entry equals the current title
					// add it to the queue
					if (q.peek().getTitle().equals(i.getTitle()) && found == false){
						found = true;
						q.add(i);
					}
				}

				// if not found, create a new queue and add it to the list.
				if (!found){
					Queue<Input> temp = new LinkedList<Input>();
					temp.add(i);
					masterInputList.add(temp);
				}
			}
			//set each master state to cover original states
			for (Queue<Input> q: masterInputList){
				boolean contained = false;
				List<Integer> stateList = new ArrayList<Integer>();
				
				for (Input i : q) {
					stateList.add(i.getNextState().getID());
				}
				
				
				State temp = new State(0);
				for (State state : TrueDFAList) {
					int numMatches = 0;
					for (Integer i : state.getIDList()) {
						if (stateList.contains(i)) {
							numMatches++;
						}
					}
					if (numMatches == stateList.size()) {
						contained = true;
						temp = state;
						break;
					}
				}
				if (contained) {
					currState.addInput(new Input(q.peek().getTitle(), temp));
				}
				
				//If this node is not already in the list, create it and throw it in
				if (!contained){
					//Create a new state for those contained
					State newState = new State(stateNum++);
					//push it onto the stack
					masterStack.push(newState);
					TrueDFAList.add(newState);
					currState.addInput(new Input(q.peek().getTitle(), newState));
					
					//Grab all the ID's from the next states and throw them into a list
					//Also check for finished
					for (Input i: q){
						newState.addID(i.getNextState().getID());
						if (i.getNextState().isFinishState()){
							newState.setFinishState(true);
						}
					}
					
					//for each input in the queue, get the state it points to
					//and add it's inputs to the masters'
//					for (Input i: q){
//						//newState.addInput(i);
//						for (Input nextInput: i.getNextState().getInputs()){
//							//If this input links back to the same state, or one in the queue,
//							//create a new input and link it back to this state.
//							if (newState.getIDList().contains(nextInput.getNextState().getID())){
//								newState.addInput(new Input(nextInput.getTitle(),newState));
//							}
//							else{
//								newState.addOldInput(nextInput);
//							}
//						}
//					}
					
					for (Integer i : newState.IDList) {
						for (State s : this.States) {
							if (s.getID() == i) {
								for (Input input : s.getInputs()) {
									newState.addOldInput(input);
								}
							}
						}
					}
				}
			}
		}
		
		
		
		//This occurs once the True list is complete
		//iterate through the list and make sure each old input has a corresponding new input
//		for (State s: TrueDFAList){
//			for (Input oi: s.getOldInputs()){
//				boolean found = false;
//				//Compare the old input with all current inputs
//				for (Input ni: s.getInputs()){
//					//if old == current, move on to the next one
//					if (oi.getTitle().equals(ni.getTitle())){
//						found = true;
//					}
//				}
//				//if there is not an equivalent for the old,
//				//find what the old input pointed to in the true list
//				//and create a new input pointing at that.
//				if (!found){
//					for (State checkStates: TrueDFAList){
//						if (checkStates.getIDList().contains(oi.getNextState().getID())){
//							s.addInput(new Input(oi.getTitle(),checkStates));
//							break;
//						}
//					}
//				}
//			}
//		}
		return TrueDFAList;
	}
	
	/**
	 * Simple matching method.  Returns if the IDs are the same or not
	 * @param list1  The first list of states to be compared
	 * @param list2  The second list of states to be compared
	 * @return
	 */
	private boolean doesMatch(List<State> list1, List<State> list2){

		if(list1.size()!=list2.size()){
			return false;
		}
		int size = list1.size();
		List<Integer> stateIDs = new ArrayList<Integer>();
		int sizeCheck=0;
		//Make the list of idMatches
		for(int k=0; k<size; k++){
			State state = list1.get(k);			
			stateIDs.add(state.getID());
		}
		
		for(int x=0; x<size; x++){
			int ID = (Integer) stateIDs.get(x);
			if(stateIDs.contains(ID)){
				sizeCheck++;
			}
		}
		
		if(sizeCheck==size){
			return true;
		}
		
		return false;
	}
}
